import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

/**
 * @Classname GreedyAlgorithm 贪心算法
 * @Description 在每一步选择中都采取最好或者最优的选择。结果导致结果是最好或者最优
 * 最佳应用---集合覆盖：电台覆盖
 *
 *
 * @Date 2021/12/23 15:15
 * @Created K024851
 */
public class GreedyAlgorithm {
    public static void main(String[] args) {
        //创建广播电台，放入集合中
        HashMap<String , HashSet<String>>  broadcasts = new HashMap<>();
        //
        HashSet hs1 = new HashSet();
        hs1.add("北京");
        hs1.add("上海");
        hs1.add("天津");
        HashSet hs2 = new HashSet();
        hs2.add("广州");
        hs2.add("北京");
        hs2.add("深圳");
        HashSet hs3 = new HashSet();
        hs3.add("成都");
        hs3.add("上海");
        hs3.add("杭州");
        HashSet hs4 = new HashSet();
        hs4.add("上海");
        hs4.add("天津");
        HashSet hs5 = new HashSet();
        hs5.add("杭州");
        hs5.add("大连");
        broadcasts.put("K1",hs1);
        broadcasts.put("K2",hs2);
        broadcasts.put("K3",hs3);
        broadcasts.put("K4",hs4);
        broadcasts.put("K5",hs5);

        HashSet all = new HashSet();
        all.add("北京");
        all.add("上海");
        all.add("天津");
        all.add("广州");
        all.add("深圳");
        all.add("成都");
        all.add("杭州");
        all.add("大连");

        ArrayList selects = new ArrayList<>();
        HashSet tempSet = new HashSet();
        String maxKey = null;
        while (all.size() !=0){
            maxKey =null;
            for (String key: broadcasts.keySet()) {
                tempSet.clear();
                HashSet areas = broadcasts.get(key);
                tempSet.addAll(areas);
                tempSet.retainAll(all);
                if (tempSet.size()>0&& (maxKey ==null ||tempSet.size()>broadcasts.get(maxKey).size())){
                    maxKey = key;
                }
                if (maxKey!=null){
                    selects.add(maxKey);
                    all.removeAll(broadcasts.get(maxKey));
                }

            }
        }
        System.out.println(selects);
    }



}
